package simple;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/4/11 17:17
 */
public class No53_最大子序和 {
    public static void main(String[] args) {
        Solution53 solution53 = new Solution53();
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -8, 7, -9};
        int result = solution53.maxSubArray(nums);
        System.out.println();
    }
}

class Solution53 {
    public int maxSubArray(int[] nums) {
        //空间复杂度为O(1)
        int length = nums.length;
        int max = nums[0];
        for (int i = 1; i < length; i++) {
            if (nums[i - 1] >= 0) {
                //后面会更大,将nums[i] 当成current
                nums[i] = nums[i - 1] + nums[i];
            } else {
                //current = nums[i]
                nums[i] = nums[i]; //这段代码比较奇怪
            }
            max = Math.max(max, nums[i]);
        }
        return max;
    }
}

    //public int maxSubArray(int[] nums) {
    //    //O3,nlogn->一次遍历 on
    //    int current = 0;
    //    int max = Integer.MIN_VALUE;
    //    int length = nums.length;
    //    for (int i = 0; i < length; i++) {
    //        if (current >= 0) {
    //            //继续加,后面出现的结果可能更大
    //            current += nums[i];
    //        } else {
    //            //当前值小于0,后面加的列都会比不要当前值要小,所以直接去掉当前值
    //            current = nums[i];
    //        }
    //        max = Math.max(current, max);
    //    }
    //    return max;
    //}

    //public int maxSubArray(int[] nums) {
    //    //分治
    //    return getSubCrossSum(nums, 0, nums.length - 1);
    //}
    //
    //public int getSubCrossSum(int[] nums, int start, int end) {
    //    if (start == end) {
    //        return nums[start];
    //    }
    //    int mid = (start + end) / 2;
    //
    //    //框架
    //    int leftSum = getSubCrossSum(nums, start, mid);
    //    int rightSum = getSubCrossSum(nums, mid + 1, end);
    //
    //    //横穿
    //    //从索引开始往左边走,找最大
    //    int maxLeftCrossSum = Integer.MIN_VALUE; //记录最大
    //    int leftCrossSum = 0; //记录每次相加的和
    //    for (int i = mid; i >= 0; i--) {
    //        leftCrossSum += nums[i];
    //        maxLeftCrossSum = Math.max(maxLeftCrossSum, leftCrossSum);
    //    }
    //
    //
    //    //从索引+1开始往右边走,找最大
    //    int maxRightCrossSum = Integer.MIN_VALUE;
    //    int rightCrossSum = 0;
    //    for (int i = mid + 1; i <= end; i++) {
    //        rightCrossSum += nums[i];
    //        maxRightCrossSum = Math.max(maxRightCrossSum, rightCrossSum);
    //    }
    //
    //    //获取横穿最大
    //    int crossSum = maxLeftCrossSum + maxRightCrossSum;
    //
    //    //获取leftSum,rightSum,crossSum最大值
    //    //拿大的
    //    int tmpSum = leftSum > rightSum ? leftSum : rightSum;
    //    int result = tmpSum > crossSum ? tmpSum : crossSum;
    //    return result;
    //
    //}

    //public int maxSubArray(int[] nums) {
    //    //暴力法
    //    //最大子序
    //    int maxSum = -Integer.MAX_VALUE;
    //    //子序和
    //    int sum = 0;
    //    int length = nums.length;
    //    for (int time = 1; time <= nums.length; time++) {
    //        //第time轮
    //        for (int i = 0; i <= length - time;i++) {
    //            sum = 0;
    //            //每次子序计算
    //            for (int j = i; j <= i + time - 1; j++) {
    //                sum += nums[j];
    //            }
    //            maxSum = Math.max(maxSum, sum);
    //        }
    //    }
    //    return maxSum;
    //}